package com.zdb.algorithm.kmp;

import java.util.Arrays;

public class KMPAlgorithm {

    public static void main(String[] args) {
        String str = "BBC ABCDABCABCDABCDABDE";
        String subStr = "ABCDABD";

        int[] next = kmpNext(subStr);
        System.out.println("next:" + Arrays.toString(next));

        // 15
        System.out.println("index=" + kmpSearch(str, subStr, next));
    }

    /**
     * kmp 查找str1中subStr第一次出现的位置
     * @param str1 源字符串
     * @param subStr 需要查找的子串
     * @param next kmp匹配表
     * @return 第一次出现的位置，-1为找不到
     */
    public static int kmpSearch(String str1, String subStr, int[] next) {

        // i为str1的位置， j为subStr的位置
        for (int i = 0, j = 0; i < str1.length(); i++) {

            // 暴力破解法，如果匹配不上，则需要将i,j 都退 j位，继续比较
            /**
            if(str1.charAt(i) != subStr.charAt(j)) {
                i = i - j;
                j = 0;
                continue;
            }
             */


            // kmp 解法，如果匹配不上，不需要退j位,
            // 当j>0时，代表着之前有j个元素匹配上了，
            while(j > 0 && str1.charAt(i) != subStr.charAt(j)) {
                j = next[j-1];
            }


            // 如果匹配上，j ++, 下一个循环i++, 同时比较下一个
            if(str1.charAt(i) == subStr.charAt(j)) {
                j++;
            }
            if(j == subStr.length()) {
                return i+1 - j;
            }

        }

        return -1;
    }

    /**
     * 获取dest字符串的kmp匹配表
     * @param dest
     * @return
     */
    public static int[] kmpNext2(String dest) {
        int[] next = new int[dest.length()];
        // 一个字符的公共长度为0
        next[0] = 0;

        // 从第二位开始，计算所有可能子串的kmp公共长度
        for (int i = 1; i < dest.length(); i++) {
            // 子串
            String subStr = dest.substring(0, i+1);

            // 比较在前缀和后缀中相同的部分，并得到相同部分的长度
            // 前缀的范围[0,i-1]
            // 后缀的返回[1, i]

            // 方法一：拿相同长度的前后缀比较
            for (int j = 0; j < i; j++) {
                // j为前后缀的长度
                if(subStr.substring(0, j+1).equals(subStr.substring(i-j, i+1))) {
                    // 说明这个长度是匹配的
                    next[i] = Math.max(next[i], j+1);
                }
            }

        }

        return next;
    }


    /**
     * 获取dest字符串的kmp匹配表
     * @param dest
     * @return
     */
    public static int[] kmpNext(String dest) {
        int[] next = new int[dest.length()];
        // 如果字符串的长度为1，部分匹配值为0
        next[0] = 0;

        for (int i = 1,j=0; i < dest.length(); i++) {
            // 当dest.charAt(i) != dest.chatAt(j),我们需要从next[j-1]获取新的j
            // 直到我们发现有 dest.charAt(i) == dest.chatAt(j)成立才退出
            // 这是kmp算法的核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
                j = next[j-1];
            }

            // 当dest.charAt(i) == dest.chatAt(j)满足时，部分匹配值就+1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }



        return next;
    }
}
